package se.study.binaryheap;

import java.util.Arrays;

/**
 * @Author tiger
 * @Description 二叉堆快速排序
 * @Date 9:42 2018/9/11
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        heapSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] arr) {
        // 1.把无序数组构建成二叉堆。从最后一个父节点开始下沉
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            HeapOperator.downAdjust(arr, i, arr.length);
        }
        System.out.println("得到的二叉堆：" + Arrays.toString(arr));

        System.out.println("开始排序...");
        // 2.循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。
        for (int i = arr.length - 1; i > 0; i--) {
            // 最后一个元素和第一个元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 下沉调整
            HeapOperator.downAdjust(arr, 0, i);
        }
    }

}
